1. Field of the Invention
This invention relates generally to data processing systems and more particularly to address development hardware and techniques.
2. Description of the Prior Art
In the early days of computers an intimate knowledge of the structure and operating characteristics of the computer were essential in order to utilize it effectively and solve problems. The primary application of computers then was mathematical computation, with minimal utilization by business and government. Programs were written in the language of the computer, for esoteric applications and were generally of interest to the person generating the program or his organization. Moreover the programmer was generally the only person who could anticipate how the computer would react when his program was in the machine; hence his presence at the computer console was required during running of his program in order to correct for unexpected occurrences. During those early days standardization and documentation of programs was practically non-existent.
As the capabilities of the computer became recognized and more particularly with improvements in computer speeds and input/output equipment, and with the advent of high level languages such as FORTRAN and COBOL which permitted the writing of programs symbolically the range of computer applications was extended. Standardized programs under control of an operating system (control program) took over functions previously reserved by necessity for the programmer, and the concept of a single program on which a single processor computed for long periods of time without access to the outside world gave way to batch processing. The batch operating system permitted the grouping of a number of jobs for the purpose of compiling or assembling the source decks into object decks (i.e. translating the user program from symbolic language to machine language), loading and executing the user's programs. Since second generation computers were much faster than their earlier counterparts, the amount of "set up" time required to prepare a computer program for execution in a computer was disproportionately large in comparison to the actual execution time of the program. The batch operating system helped solve this problem. Moreover the batch operating system introduced the concept of a supervisor state and user or problem state for computer operation.
With the reduction of computer set-up time to a negligible percentage of computer run-time for a given job, computers became more attractive for data processing uses other than pure mathematical calculation uses.
However, with the increased usage of computers by business and government organizations there came an increased demand for greater efficiency and operating systems that provided all the services and control to permit jobs to be scheduled and executed in a multiprogramming environment; the third generation computer rose to meet the challenge.
In simple batched systems the important resource of random access memory (generally core memory, but more recently MOS-metal oxide semiconductor memory) was allocated to a single program, and proved to be wasteful of core memory whenever the program did not need the entire memory. One of the first problems of a multiprogramming scheme was the efficient utilization of main memory particularly when several system functions invoked the same procedure. As a first step core memory was partitioned which permitted multiple programs to reside in separate areas of core memory at the same time. However, since programs are rarely of the same size, overlapping of areas with concomitant overlay of one program by another was always a threat. To alleviate this situation nonoverlapping areas of the address space were allocated to each program. This technique partially solved the above problem of overlap but introduced the problem of fragmentation of core memory i.e. "holes" or unused portions of core memory which were too small for any other allocation and hence wasted that portion of core. A solution to the problem of fragmentation of core memory was to provide a relocation register to translate contiguous addresses in name space into contiguous addresses into memory space. This resulted in giving the system freedom in the assignment of physical memory locations and permitted in relocation of name space so as to condense the unused portions of physical main memory into one continuous part of core. Still there remained much inefficiency in the use of main memory because this constant reallocation of main memory was wasteful, and created severe penalties in supervision overhead particularly where many concurrent programs were continually changing their demands on main memory. The next step in the evolution of efficient memory utilization was the introduction of the concept of paging. Paging is a method of memory allocation wherein the name-space of program is subdivided into equal portions or pages, and physical main memory is subdivided into equal portions or blocks and wherein the page size is equal to the block size although the total name space need not be equal to the physical main memory. A block index is utilized to associate any particular block with any particular page, hence it is not necessary to relocate or move a page with each program demand. One free block is as good as another in which to assign a page since continuity in a program is obtained via the block index, and the probability is high that a free block can be found for a new page in main memory. Some computer systems that utilize paging are the Atlas Computer of Manchester University, XDS940, and Honeywell Information Systems HIS 645.
Although the paging technique solved the problem of allocating main memory space among several programs, it did not solve the problem of allocating addresses in name space among several programs nor the problem of protection of information in main memory. A. W. Holt first suggested the concept of segmentation (Program Organization and Record Keeping for Dynamic Storage Allocation, Information Processing 62, North-Holland Publishing Co., Amsterdam, 1962, p. 539.) and J. B. Dennis further developed the concept of segmentation in order to solve problems pertaining to the naming and referencing of information (Segmentation of the Design of Multiprogrammed Computer Systems, Journal of the Association for Computing Machinery, Vol. 12, No. 4, October 1965, pp. 589-602.) Early uses of the segmentation concept were in the Burroughs B5000 computer, and also in the Honeywell Information Systems HIS 645 utilizing the Multics operating system.
In the segmentation scheme a segment is defined as an ordered set of words which are referenced by a segment name that distinguishes the segment from all other segments, and by an integer address that is utilized to select a particular member from the ordered set of uses in the segment. The segment is the unit of user sharing, carries a symbolic name, has a set of associated access attributes which describes, among other things, the function in which each user is permitted to reference the contained procedures and/or data. The segment is permitted to grow and shrink and is directly addressable in programs. The segment is thought of as an extention of the notion of file found in traditional systems; however, the file is not directly addressable nor can files copied into core be directly shared by programs of other users.
The segmentation concept is a reasonable solution to the problem of naming, addressing, allocating and protecting information in main memory such that:
1. A computation should have the use of a name space sufficiently large that all information it references may be assigned unique names, and such that reallocation of information within its name space is never necessary.
2. Data objects of a computation should be expandable without requiring a reallocation of name space.
3. Information referenced in common by several computations should have the same name for all computations that reference it.
4. A protection mechanism should operate in name space to permit access to information by a computation only in an authorized manner. (Jack B. Dennis, Segmentation and the Design of Multiprogrammed Computer Systems, Journal of the Association of Computing Machinery, Vol. 12, No. 4, October 1965, pp. 589-602.)
Whereas some computer systems referenced supra utilize some of the concepts of paging, blocking and segmentation to improve efficiency of memory utilization, the use of these techniques have not been fully exploited being implemented generally in systems software with some minimum of hardware. For example the HIS 645, utilizing some of the concepts of paging and segmentation, is an upgraded HIS 635 which was modified to include multiple memory modules, multiple input/output controllers, multiprocessors, and a series of special registers called attachment registers. Together with a virtual memory concept and the MULTICS software package the HIS 645 computer incorporates some of the concepts supra.
As the fourth generation computer system begins to take shape it will undoubtedly exhibit the best characteristics of the third generation computer system, such as paging and segmentation. What is needed, however, is an improved version of segmentation with improved segmented addressing techniques and segmented addressing hardware.